#BST

class BST:
    '''
       二叉搜索树，不包含重复元素
    '''
    class BNode:
        def __init__(self, value=None):
            self.value = value
            self.left = None
            self.right = None

    def __init__(self):
        self.root = None
        self.size = 0

    def __len__(self):
        return self.size
    def __contains__(self, value):
        return self._contains(self.root, value)
    def __str__(self): #中序遍历打印
        result = []
        def inorder(tree):
            if tree:
                inorder(tree.left)
                result.append(tree.value)
                inorder(tree.right)
        inorder(self.root)
        return f'BST({self.size}):{result}'

    def is_empty(self):
        return self.size == 0

    def add(self, value):
        def _add(node, value):
            add_node = self.BNode(value)
            if node is None:
                self.size += 1
                return add_node
            if value < node.value:
                node.left = _add(node.left, value)
            elif value > node.value:
                node.right = _add(node.right, value)
            return node
        self.root = _add(self.root, value)

    def _contains(self, node, value):
        if node is None:
            return False
        if value == node.value:
            return True
        elif value < node.value:
            return self._contains(node.left, value)
        else:
            return self._contains(node.right, value)

    def _minimum(self, node):
        if node.left is None:
            return node
        return self._minimum(node.left)

    def _remove_min(self, node):
        if node.left is None:
            right_node = node.right
            node.right = None
            self.size -= 1
            return right_node
        node.left = self._remove_min(node.left)
        return node

    def remove(self, value):
        self.root = self._remove(self.root, value)

    def _remove(self, node, value):
        if node is None:
            return None
        if node.value == value:
            if node.left is None:
                right_node = node.right
                node.right = None
                self.size -= 1
                return right_node
            elif node.right is None:
                left_node = node.left
                node.left = None
                self.size -= 1
                return left_node
            else:
                successor = self._minimum(node.right)
                successor.right = self._remove_min(node.right)
                successor.left = node.left
                node.left = None
                node.right = None
                return successor
        elif value < node.value:
            node.left = self._remove(node.left, value)
        else:
            node.right = self._remove(node.right, value)
        return node

    def min(self):
        if self.size == 0:
            raise IndexError("BST is empty")
        return self._minimum(self.root).value

    def max(self):
        if self.size == 0:
            raise IndexError("BST is empty")
        def _maximum(node):
            if node.right is None:
                return node
            return _maximum(node.right)
        return _maximum(self.root).value





if __name__ == "__main__":
    bst = BST()
    bst.add(25)
    bst.add(20)
    bst.add(18)
    bst.add(19)
    bst.add(67)
    bst.add(30)
    print(bst)
    print(bst.max())

    bst.remove(18)
    bst.remove(67)
    print(bst)

    bst.remove(25)
    print(bst)
